public class Solution {
    public static String longestCommonPrefix(String[] strs) {
        if(strs == null || strs.length == 0){
            return "";
        }
        int count = strs.length;
        String prefix = strs[0];
        for (int i = 1; i < count; i++) {
            prefix = longestCommonPrefix(prefix, strs[i]);
            if(prefix.isEmpty()) {
                break;
            }
        }
        return prefix;
    }
    public static String longestCommonPrefix(String str1, String str2) {
        int length = Math.min(str1.length(), str2.length());
        int index = 0;
        while(index < length && str1.charAt(index) == str2.charAt(index)) {
            index++;
        }
        return str1.substring(0,index);
    }
    public static void main(String[] args) {
        String[] s = {"flower","flow","flight"};
        System.out.println(longestCommonPrefix(s));
//        System.out.println(climbStairs(5));
//        System.out.println(fib(5));
    }
}
//public static String longestCommonPrefix(String[] strs) {
//    String string = "";
//    int len = strs[0].length();
//    for (int i = 1; i < strs.length; i++) {
//        len = Math.min(strs[i].length(), len);
//    }
//    for (int i = 0; i < len; i++) {
//        char ret = strs[0].charAt(i);
//        for(int j = 0; j < strs.length; j++){
//            if(strs[j].charAt(i) != ret)
//                return string;
//        }
//        string += ret;
//    }
//    return string;
//}


//public static int romanToInt(String s) {
//    int len = s.length();
//    int sum = 0;
//    for (int i = 0; i < len; i++) {
//        if(s.charAt(i) == 'I'){
//            if(i + 1 < len && (s.charAt(i + 1) == 'V' || s.charAt(i + 1) == 'X')) {
//                sum -= 1;
//            } else sum += 1;
//        } else if (s.charAt(i) == 'X') {
//            if(i + 1 < len && (s.charAt(i + 1) == 'L' || s.charAt(i + 1) == 'C')) {
//                sum -= 10;
//            } else sum += 10;
//        }else if (s.charAt(i) == 'C') {
//            if(i + 1 < len && (s.charAt(i + 1) == 'D' || s.charAt(i + 1) == 'M')) {
//                sum -= 100;
//            } else sum += 100;
//        }else{
//            sum += numOfChar(s.charAt(i));
//        }
//    }
//    return sum;
//}
//public static int numOfChar(char ret){
//    if(ret == 'V') return 5;
//    else if(ret == 'L') return 50;
//    else if(ret == 'D') return 500;
//    else return 1000;
//}

//    public static int fib(int n) {
//        if(n == 0 || n == 1){
//            return n;
//        }
//        int f1 = 0;
//        int f2 = 1;
//        for (int i = 2; i <= n; i++) {
//            int tmp = f2;
//            f2 = f1 + f2;
//            f1 = tmp;
//        }
//        return f2;
//    }


//    public static int climbStairs(int n) {
//        if(n == 1 || n == 2){
//            return n;
//        }
//        int x1 = 1;
//        int x2 = 2;
//        while(n - 2 > 0)
//        {
//            int tmp = x2;
//            x2 = x1 + x2;
//            x1 = tmp;
//            n--;
//        }
//        return x2;
//    }